/*
 * @Author: Mainul Islam
 */

package edu.uta.cse.randomgraph.graph;

import java.awt.Graphics;
import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import edu.uta.cse.randomgraph.graph.property.Node;
import edu.uta.cse.randomgraph.util.LogType;
import edu.uta.cse.randomgraph.util.LogWriter;

public abstract class MyGraph {

	public int numNodes;
	public int numNodesAfterDelete;
	public int numEdges;
	public int diameter;
	public int numConComp;
	public int maxSizeConComp;
	public double avgClusCo;
	protected Node nodes[];
	protected boolean edgeMat[][];
	protected int dist[][];
	protected int conCompSize[];
	protected boolean visitedNodes[];
	protected List<Integer> degreeValueList;
	protected List<Integer> deleteNodeIndex;
	protected int degreeDistribution[];
	
	protected boolean isCoordinatesGenerated;
	protected boolean drawConComp, drawStructuredView;
	public boolean contSimulation;
	protected int nodeDiam, nodeRad;
	private int prevWidth, prevHeight;
	protected int MAX_DELAY;
	protected static int QUICK_DELAY = 50;
	protected static int numSlowNodes = 5;
	protected String prevView;


	public MyGraph(int nodeNum) {
		numNodes = nodeNum;
		initGraph();
	}

	private void initGraph() {
		numEdges = 0;
		diameter = 0;
		numConComp = 0;
		maxSizeConComp = 0;
		avgClusCo = 0;
		nodes = new Node[numNodes+1];
		edgeMat = new boolean[numNodes+1][numNodes+1];
		dist = new int[numNodes+1][numNodes+1];
		
		initDrawComponents();
	} 
	
	private void initDrawComponents() {
		isCoordinatesGenerated = false;
		drawConComp = false;
		drawStructuredView = true;
		contSimulation = false;
		nodeDiam = 8;
		nodeRad = nodeDiam/2;
		prevWidth = prevHeight = 0;
	}
	
	protected void initDist() {
		for(int i=0; i<numNodes; i++) {
			Arrays.fill(dist[i], Integer.MAX_VALUE);
			dist[i][i] = 0;
		}
	}
	
	public void setDelay(int val) {
		this.MAX_DELAY = val;
	}

	public Node[] getNodes() {
		return this.nodes;
	}
	
	public boolean[][] getEdgeMatrix() {
		return this.edgeMat;
	}
	
	public void setDrawConComp(boolean val) {
		this.drawConComp = val;
	}
	
	public void alterDrawConComp() {
		this.drawConComp = !this.drawConComp;
	}
	
	public void setDrawStructuredView(boolean val) {
		if(this.drawStructuredView)
			prevView = "Structured";
		else
			prevView = "Random";
		this.drawStructuredView = val;
	}
	
	public void alterDrawStructuredView() {
		if(this.drawStructuredView)
			prevView = "Structured";
		else
			prevView = "Random";
		this.drawStructuredView = !this.drawStructuredView;
	}

	
	public void setContinueSimulation(boolean val) {
		this.contSimulation = val;
	}

	public void setPrevHeightWidth(int currWidth, int currHeight) {
		this.prevWidth = currWidth;
		this.prevHeight = currHeight;
	}
	
	protected boolean isHeightWidthChanged(int currWidth, int currHeight) {
		if(this.prevWidth != currWidth)
			return true;
		if(this.prevHeight != currHeight)
			return true;
		return false;
	}

	protected void computeDegreeList() {
		degreeValueList = new ArrayList<Integer>();
		degreeDistribution = new int[numNodes+1];
		for(int i=0; i<numNodes; i++) {
			if( !degreeValueList.contains( nodes[i].deg ) ) {
				degreeValueList.add(nodes[i].deg);
				degreeDistribution[nodes[i].deg] = 1;		
			}
			else {
				degreeDistribution[nodes[i].deg]++;		
			}
		}
		Collections.sort(degreeValueList);
		return;
	}
	
	protected void computeFloydWarshal() {
		int i, j, k;
		int N = numNodes;
		for(i=0; i<N; i++)
			for(j=0; j<N; j++)
				for(k=0; k<N; k++)
				{
					if(dist[i][k] == Integer.MAX_VALUE || dist[k][j] == Integer.MAX_VALUE)
						continue;
					
					if(dist[i][k] + dist[k][j] < dist[i][j])
						dist[i][j] = dist[i][k] + dist[k][j];
				}
	}
	
	protected void computeDiameter() {
		int i, j;
		int N = numNodes;
		int maxVal = 0;
		for(i=0; i<N; i++) {
			if(nodes[i].deg == 0) {
				maxVal = -1;
				break;
			}
			for(j=0; j<N; j++) {
				if(dist[i][j]!=Integer.MAX_VALUE) 
					if(dist[i][j]>maxVal)
						maxVal = dist[i][j];
			}
		}
		this.diameter = maxVal;
	}

	private void setMaximumSizeofConnectedComponents() {
		int maxVal = 0;
		for(int i=1; i<=numConComp; i++) {
			if(conCompSize[i] > maxVal)
				maxVal = conCompSize[i];
		}
		this.maxSizeConComp = maxVal;
	}

	protected void computeConnectedComponents() {
		visitedNodes = new boolean[numNodes+1];
		conCompSize = new int[numNodes+1];
		int sz, r = 0;
		int r0 = 0;
		for(int i=0; i<numNodes; i++) {
			if( !visitedNodes[i] ) {
				if(nodes[i].deg == 0) {
					visitedNodes[i] = true;
					conCompSize[0] = 1;
					nodes[i].setConCompRank(0);
					r0++;
					continue;
				}
				sz = computeConComp(i, ++r);
				conCompSize[r] = sz;
			}
		}
		this.numConComp = r+r0;
		setMaximumSizeofConnectedComponents();
		return;
	}
	
	// return the size of the component
	private int computeConComp(int n, int r) {
		visitedNodes[n] = true;
		nodes[n].setConCompRank(r);
		int sz = 1;
		for(int i=0; i<numNodes; i++) {
			if(edgeMat[n][i] && !visitedNodes[i])
				sz += computeConComp(i, r);
		}
		return sz;
	}
	
	private void computeAverageClusteringCoefficient() {
		int i, j, k, n;
		int u, v;
		int count;
		double comp, val, res = 0.0;
		
		if(numNodes <= 0)
			return;
		
		for(i=0; i<numNodes; i++) {
			n = nodes[i].edgeList.size();
			count = 0;
			for(j=0; j<n; j++) {
				u = nodes[i].edgeList.get(j);
				for(k=j+1; k<n; k++) {
					v = nodes[i].edgeList.get(k);
					if(edgeMat[u][v])
						count++;
				}
			}
			comp = (nodes[i].deg*(nodes[i].deg-1)) / 2;
			if(comp > 0)
				val = (double)count/comp;
			else
				val = 0;
			res += val;
			nodes[i].setClusteringCoefficient(val);
		}
		this.avgClusCo = res/numNodes;
	}


	public int getDiameter() {
		computeDiameter();
		return this.diameter;
	}
	
	public int getNumberOfConnectedComponents() {
		computeConnectedComponents();
		return this.numConComp;
	}

	public int getMaximumSizeofConnectedComponents() {
		computeConnectedComponents();
		return this.maxSizeConComp;
	}

	public double getAverageClusteringCoefficient() {
		computeAverageClusteringCoefficient();
		return this.avgClusCo;
	}
	
	public boolean deleteNodes(int delVal) {
		deleteNodeIndex	= new ArrayList<Integer>();
		int numNodesToDelete = (int)(numNodes * (double)delVal/100.0);
		int i, r;
		
		if(numNodesToDelete <= 0)
			return false;
		
		Random rand = new Random();
		for(i=0; i<numNodesToDelete; i++) {
			r = rand.nextInt(numNodes);
			if(deleteNodeIndex.contains(r))
				i--;
			else 
				deleteNodeIndex.add(r);
		}
		updateNodeAfterDelete();
		return true;
	}
	
	private void updateNodeAfterDelete() {
		int i, j;
		int numNodesToDelete = deleteNodeIndex.size();
		int newNumNodes = numNodes - numNodesToDelete;
		int newNumEdges = 0;
		int newIndices[] = new int[numNodes+1];
		
		boolean newEdgeMat[][] = new boolean[newNumNodes +1][newNumNodes+1];
		Node newNodes[] = new Node[newNumNodes+1];
		int newDist[][] = new int[newNumNodes+1][newNumNodes+1];
		
		for(i=0; i<newNumNodes; i++) {
			Arrays.fill(newDist[i], Integer.MAX_VALUE);
			newDist[i][i] = 0;
		}

		for(int ind: deleteNodeIndex) {
			nodes[ind].isDeleted = true;
		}
		
		j=0;
		for(i=0; i<numNodes; i++) {
			if(nodes[i].isDeleted)
				newIndices[i] = -1;
			else {
				newNodes[j] = new Node();
				newNodes[j].X = nodes[i].X;
				newNodes[j].Y = nodes[i].Y;
				newIndices[i] = j;
				j++;
			}
		}
		
		for(i=0; i<numNodes-1; i++) {
			for(j=i+1; j<numNodes; j++) {
				if(edgeMat[i][j]) {
					if(nodes[i].isDeleted || nodes[j].isDeleted) {
						edgeMat[i][j] = edgeMat[j][i] = false;
						dist[i][j] = dist[j][i] = 0;
						numEdges--;
					}
				}
			}
		}
		
		int u, v;
		newNumEdges = 0;
		for(i=0; i<numNodes-1; i++) {
			u = newIndices[i];
			for(j=i+1; j<numNodes; j++) {
				if(edgeMat[i][j]) {
					v = newIndices[j];
					newEdgeMat[u][v] = newEdgeMat[v][u] = true;
					newDist[u][v] = newDist[v][u] = 1;
					newNumEdges++;
					newNodes[u].deg++;
					newNodes[v].deg++;
					newNodes[u].edgeList.add(v);
					newNodes[v].edgeList.add(u);
				}
			}
		}
		
		numNodes = newNumNodes;
		numEdges = newNumEdges;
		nodes = newNodes;
		edgeMat = newEdgeMat;
		dist = newDist;
		
		computeFloydWarshal();
		computeDegreeList();
	}
	
	protected void writeDegreeDistribution(LogWriter lw) {
		computeDegreeList();
		
		DecimalFormat df = new DecimalFormat("#.########");
		
		for(int i=0; i<numNodes; i++) {
			if(degreeDistribution[i] > 0) {
				lw.write( String.format("%5s", i));
				lw.write( String.format("%5s", "->"));
				lw.write( String.format("%5s", degreeDistribution[i]));
				lw.write( String.format("%15s", df.format( (double)degreeDistribution[i]/(2*numEdges)) ));
				lw.writeLine();
			}
		}
	}


	protected void writeAgeDegreeRelation(LogWriter lw) {
		for(int i=0; i<numNodes; i++) {
			lw.write( String.format("%5s", i));
			lw.write( String.format("%5s", nodes[i].age));
			lw.write( String.format("%5s", nodes[i].deg));
			lw.writeLine();
		}
	}


	public abstract void generateGraph();
	public abstract void drawGraph(int currWidth, int currHeight, Graphics g);
	public abstract void writeInfo(LogWriter lg, LogType lt);

}
